import java.util.ArrayList;
import java.util.List;

/**
 * @program: LeetCode
 * @description: LeetCode : 120. 三角形最小路径和
 * @author: WXY
 * @create: 2023-01-10 10:33
 * @Version 1.0
 **/
public class Num120_minimumTotal {
    public static int minimumTotal1(List<List<Integer>> triangle) {
        int len = triangle.size();
        for (int i = len - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                int num = Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)) + triangle.get(i).get(j);
                triangle.get(i).remove(j);
                triangle.get(i).add(j, num);
            }
        }
        return triangle.get(0).get(0);
    }


    public static int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size();
        int n = triangle.get(len - 1).size();
        int[][] dp = new int[len][n];
        if (len == 1) {
            return triangle.get(0).get(0);
        }
        if (len == 2) {
            return triangle.get(0).get(0) + Math.min(triangle.get(1).get(0), triangle.get(1).get(1));
        }
        dp[0][0] = triangle.get(0).get(0);
        dp[1][0] = dp[0][0] + triangle.get(1).get(0);
        dp[1][1] = dp[0][0] + triangle.get(1).get(1);
        int min = Integer.MAX_VALUE;
        for (int i = 2; i < len; i++) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                int curNum = triangle.get(i).get(j);
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + curNum;
                    continue;
                }
                if (j == triangle.get(i).size() - 1) {
                    dp[i][j] = dp[i - 1][j - 1] + curNum;
                    continue;
                }
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + curNum;
            }
        }
        for (int i = 0; i < n; i++) {
            min = Math.min(dp[len - 1][i], min);
        }
        return min;
    }


    public static void main(String[] args) {
        List<List<Integer>> list = new ArrayList<>();
        ArrayList<Integer> list1 = new ArrayList<>();
        list1.add(2);
        ArrayList<Integer> list2 = new ArrayList<>();
        list2.add(3);
        list2.add(4);
        ArrayList<Integer> list3 = new ArrayList<>();
        list3.add(6);
        list3.add(5);
        list3.add(1);
        ArrayList<Integer> list4 = new ArrayList<>();
        list4.add(4);
        list4.add(1);
        list4.add(8);
        list4.add(3);
        list.add(list1);
        list.add(list2);
        list.add(list3);
        list.add(list4);
        int total = minimumTotal1(list);
        System.out.println(total);


        List<List<Integer>> list_1 = new ArrayList<>();
        ArrayList<Integer> list_1_1 = new ArrayList<>();
        list_1_1.add(-1);
        ArrayList<Integer> list_1_2 = new ArrayList<>();
        list_1_2.add(2);
        list_1_2.add(3);
        ArrayList<Integer> list_1_3 = new ArrayList<>();
        list_1_3.add(1);
        list_1_3.add(-1);
        list_1_3.add(-3);
        list_1.add(list_1_1);
        list_1.add(list_1_2);
        list_1.add(list_1_3);
        int i = minimumTotal1(list_1);
        System.out.println(i);

    }

}
